package com.apes.tutoring;

import java.util.Scanner;

/**
 * @author ZhangyiA
 * @describe: 采用 dfs 遍历数组判断是否存在环
 * @date 2021/07/09
 */

public class One_DependLoop {

    private int ans = 0;

    public void dfs(int[][] p , boolean[] pd , int x){
        if(pd[x]){
            ans = 1;
            return ;
        }
        pd[x] = true;
        for(int i = 0 ; i < p.length ; i ++){
            if(p[x][i] == 1){
                dfs(p , pd , i);
            }
        }
        pd[x] = false;
    }

    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        One_DependLoop loop = new One_DependLoop();
        int T = input.nextInt();
        while(T -- > 0){
            loop.ans = 0;
            int n = input.nextInt();
            int[][] p = new int[n][n];
            for(int i = 0 ; i < n ; i ++){
                for(int j = 0 ; j < n ; j ++){
                    p[i][j] = input.nextInt();
                }
            }
            boolean[] pd = new boolean[n];
            for(int i = 0 ; i < n ; i ++){
                if(!pd[i]){
                    loop.dfs(p , pd , i);
                    if(loop.ans == 1){
                        break;
                    }
                }
            }
            System.out.println(loop.ans);
        }
    }
}
/*
2
3
0 1 0
0 0 1
1 0 0
3
0 1 0
0 0 0
0 0 0
* */
